/* pplz.c -- compression algorithm from lzo & long common string
 * Pepper
 */
#include <assert.h>
#include <stdio.h>
#include "pplz.h"

/*
 *  store tttttt00 tttttttt 
 *  return the new output pointer
 */
static INLINE uchar *store_14bit(uchar *op, uint t)
{
    *op++ = (uchar)((t & 63) << 2);
    *op++ = (uchar)(t >> 6);
    return op;
}

/* 
 * store a number t must > 0 
 * return the new output pointer 
 */
static INLINE uchar *store_len(uchar *op, uint t)
{
    while(t > 255)
    {
        t -= 255;
        *op++ = 0;
    }
    ASSERT(t > 0);
    *op++ = (uchar)t;

    return op;
}

/*
 *  store the literal run
 *  from [ip] with length [t] bytes to [op];
 *  if bstart is 0, op[-2] low 2 bits must be available
 *  return the new output pointer
 */
static INLINE uchar *store_run(uchar *op, const uchar *ip, uint t, int bstart)
{
    if (bstart)
    {
        if(t <= R2_FIRST_LEN)
        {
            *op++ = (uchar)t;
        }
        else
        {
            *op++ = R1_MARKER;
            op = store_len(op, t - R1_ADD);
        }
    }
    else if (t <= R3_MAX_LEN)
    {
        op[-2] |= (uchar)t;
    }
    else if (t <= R2_MAX_LEN)
    {
        *op++ = (uchar)(t - R2_ADD);
    }
    else
    {
        *op++ = R1_MARKER;
        op = store_len(op, t - (R1_ADD + R2_ADD));
    }
    MEMCPY(op, ip, t);

    return op;
}

static INLINE uchar *store_match(uchar *op, uint m_len, uint m_off)
{
    ASSERT(M2_MAX_LEN <= M1_MIN_LEN);   /* so cannot be M1 in m_len < M2_MAX_LEN */

    if(m_len <= M2_MAX_LEN)
    {
        ASSERT(m_len >= 3); 

        if (m_off <= M2_MAX_OFFSET)         /* M2 match */
        {
            m_off -= 1;
            *op++ = (uchar)(((m_len - 1) << 5) | ((m_off & 7) << 2));
            *op++ = (uchar)(m_off >> 3);
        }
        else if (m_off <= M3_MAX_OFFSET)    /* M3 match */
        {
            m_off -= 1;
            *op++ = (uchar)(M3_MARKER | (m_len - 2));
            op = store_14bit(op, m_off);
        }
        else                                /* M4 match */
        {
            m_off -= M3_MAX_OFFSET;
            ASSERT(m_off > 0); 
            ASSERT(m_off <= 0x7fff);
            *op++ = (uchar)(M4_MARKER |
                    ((m_off & M3_MAX_OFFSET) >> 11) | (m_len - 2));
            op = store_14bit(op, m_off);
        }

        return op;
    }

    /* length > (M2_MAX_LEN)8 */
    if (m_off <= M3_MAX_OFFSET)         /* M3 match */
    {
        m_off -= 1;
        if (m_len <= M3_MAX_LEN)
        {
            *op++ = (uchar)(M3_MARKER | (m_len - 2));
        }
        else
        {
            m_len -= M3_MAX_LEN;
            *op++ = M3_MARKER | 0;
            op = store_len(op, m_len);
        }
        op = store_14bit(op, m_off);
    }
    else if(m_off <= M4_MAX_OFFSET)     /* M4 match */ 
    {
        m_off -= M3_MAX_OFFSET;
        ASSERT(m_off > 0); 
        ASSERT(m_off <= 0x7fff);
        if (m_len <= M4_MAX_LEN)
        {
            *op++ = (uchar)(M4_MARKER |
                    ((m_off & M3_MAX_OFFSET) >> 11) | (m_len - 2));
        }
        else
        {
            m_len -= M4_MAX_LEN;
            *op++ = (uchar)(M4_MARKER | ((m_off & M3_MAX_OFFSET) >> 11));
            op = store_len(op, m_len);
        }
        op = store_14bit(op, m_off);
    }
    else                                /* M1 match */
    {
        *op++ = M1_MARKER;

        *(uint *)op = (m_off << 1);
        op += 4;

        if(m_len > M1_SHORT_LEN)
        {
            op[-4] |= 1;
            *(ushort *)op = (ushort)(m_len >> 14);
            op += 2;
        }
        op = store_14bit(op, m_len);
    }
    return op;
}

/*
 *  compress buffer[in] with length in_len into buffer[out] 
 *  outbuffer bound is not checked
 *
 *  return the bytes not handled.
 */
static int do_compress(pplz_hash_t *ph, const uchar *in, uint in_len, uchar *out, uint *out_len)
{
    const uchar *const in_end = in + in_len;                /* input buffer boundary */
    const uchar *const ip_end = in + in_len - BYTES_LEFT;   /* - prefetch length */
    uchar *const op_end = out + *out_len;                  /* output buffer boundary */

    register const uchar *ip;       /* point to bytes encoding */
    const uchar *ii;                /* point to bytes already flushed */
    uchar *op;                      /* point to output buffer */

    const uchar **s_dict = ph->s_dict;
    const uchar **l_dict = ph->l_dict;
    register uint s_hash, l_hash;   /* sliding hash value */

    ii = ip = in;    
    op = out;
    ASSERT(ip < ip_end);

    /* zero hash table */
    memset(s_dict, 0, S_HASH_SIZE * sizeof(uchar *));
    memset(l_dict, 0, L_HASH_SIZE * sizeof(uchar *));

    S_HASH_FIRST(s_hash, ip);
    L_HASH_FIRST(l_hash, ip);

    while(1)
    {

//        fprintf(stderr, "in_len=%d, out_len=%d\n", in_len, *out_len);
        register const uchar *m_pos;
        uint m_off;
        uint m_len;

        /* check long range hash first */
        m_pos = l_dict[L_INDEX(l_hash)];
        if(m_pos != NULL
                && M1_CMP(m_pos, ip)
                && (m_off = ip - m_pos) >= M1_MIN_LEN
                && m_off < M1_MAX_OFFSET)
        {
            m_len = M1_MIN_LEN;
            l_dict[L_INDEX(l_hash)] = ip;
            goto match;
        }

        /* check short range hash */

        m_pos = s_dict[S_INDEX(s_hash)];
        if(m_pos != NULL
                && *(int *)m_pos == *(int *)ip
                && (m_off = ip - m_pos) >= 4
                && m_off < M4_MAX_OFFSET)
        {
            m_len = 4;
            s_dict[S_INDEX(s_hash)] = ip;
            goto match;
        }

        /* a literal, update hash */
        s_dict[S_INDEX(s_hash)] = ip;

        if(((ip - in) & L_HASH_RECORD_MARK) == 0)
        {
            l_dict[L_INDEX(l_hash)] = ip;
        }
        if(++ip >= ip_end)
        {
            break;
        }
        S_HASH_NEXT(s_hash, ip);
        L_HASH_NEXT(l_hash, ip);
        continue;

match:
        /* store current literal run */
        if (ip - ii > 0)
        {
            int t = ip - ii;
            /* output buffer boundary check */
            if(op + t + (t >> 8) + 3 >= op_end)
            {
                goto out_of_buffer;
            }
            op = store_run(op, ii, ip - ii, op == out);
            ii = ip;
        }

        /* memcmp to get match length */
        ip += m_len; /* already compared */
        m_pos += m_len;

        while(ip + 4 <= in_end && *(int *)ip == *(int *)m_pos) 
        {
            ip += 4;
            m_pos += 4;
        }
        while(ip < in_end && *m_pos == *ip)
        {
            ++ip;
            ++m_pos;
        }
        m_len = ip - ii;
        if(m_len > m_off)
        {
            /* overlap found, roll back */
            m_len = m_off;
            ip = ii + m_len;
        }
        
        /* output buffer boundary check */
        if(op + 8 >= op_end)
        {
            goto out_of_buffer;
        }
        op = store_match(op, m_len, m_off);

        /* recompute hash */
        if(m_len <= M1_MIN_LEN / 3)
        {
            do
            {
                ++ii;
                L_HASH_NEXT(l_hash, ii);
            }while(ii < ip);
        }
        else
        {
            L_HASH_FIRST(l_hash, ip); 
            ii = ip;
        }
        S_HASH_FIRST(s_hash, ip);
        
        ASSERT(ii == ip);
        if(ip >= ip_end) 
        {
            break;
        }
        if ((op-out) % 100000 <= 100)
            fprintf(stderr, "%d\t", op-out);

    }
    *out_len = op - out;
    return in_end - ii;

out_of_buffer:
    return PP_E_OUTPUT_OVERRUN;
}


int pplz_encode(pplz_hash_t *ph, const uchar *in, uint in_len, uchar *out, uint *out_len)
{
    uchar *op = out;
    int t;

    //fprintf(stderr, "in_len=%d, out_len=%d\n", in_len, *out_len);
    
    if(ph == NULL || ph->s_dict == NULL || ph->l_dict == NULL)
    {
        return PP_E_DICT_NOT_READY;
    }
    if(in_len > MAX_BUFFER_SIZE)
    {
        return PP_E_BUFFER_TOO_LARGE;
    }

    if(in_len <= BYTES_LEFT)
    {
        t = in_len;
    }
    else
    {
        t = do_compress(ph, in, in_len, op, out_len);
        op += *out_len;
    }

    if (t > 0)
    {
        const uchar *ii = in + in_len - t;
        op = store_run(op, ii, t, op == out);
    }
    else if(t < 0)
    {
        return t;
    }

    /* eof flag */
    *op++ = M4_MARKER | 1;
    *op++ = 0;
    *op++ = 0;

    *out_len = (uint)(op - out);
    return PP_E_OK;
}

int pplz_decode(const uchar *in, uint in_len, uchar *out, uint *out_len)
{
    const uchar *m_pos = NULL;
    const uchar *ip;
    const uchar * const ip_end = in + in_len;
    uchar *op;
    uchar *op_end = out + *out_len;
    uint t;

    *out_len = 0;

    op = out;
    ip = in;

    /* handle the first literal run */
    t = *ip;
    if(t < M4_MARKER && t != M1_MARKER) 
    {
        ++ip;
        if (t == R1_MARKER) 
        {
            t = 0;
            NEED_IP(1);
            while (*ip == 0)
            {
                t += 255;
                ip++;
                NEED_IP(1);
            }
            t += R1_ADD + *ip++;
        }

        /* copy literals */
        ASSERT(t > 0); NEED_OP(t); NEED_IP(t + 1);
        MEMCPY(op, ip, t); 
    }

    while (ip < ip_end)
    {
        t = *ip++;

        /* handle literals run */
        if (t < M4_MARKER && t != M1_MARKER)
        {
            /* t < 16, R1 or R2 run */
            if (t == R1_MARKER) 
            {
                t = 0;
                NEED_IP(1);
                while (*ip == 0)
                {
                    t += 255;
                    ip++;
                    NEED_IP(1);
                }
                t += R1_ADD + *ip++;
            }
            t += R2_ADD;

            /* copy literals */
            ASSERT(t > 0); NEED_OP(t); NEED_IP(t + 1);
            MEMCPY(op, ip, t); 
            continue;
        }

        /* handle matches */
        if (t >= M2_MARKER)          /* a M2 match */
        {
            NEED_IP(1);
            m_pos = op - 1;
            m_pos -= (t >> 2) & 7;
            m_pos -= *ip++ << 3;
            t = (t >> 5) + 1;
        }
        else if (t >= M3_MARKER)    /* a M3 match */
        {
            t &= 31;
            if (t == 0)
            {
                NEED_IP(1);
                while (*ip == 0)
                {
                    t += 255;
                    ip++;
                    NEED_IP(1);
                }
                t += 31 + *ip++;
            }
            t += 2;

            NEED_IP(2);
            m_pos = op - 1;
            m_pos -= (*(const ushort *)ip) >> 2;
            ip += 2;
        }
        else if (t >= M4_MARKER)    /* a M4 match */
        {
            m_pos = op;
            m_pos -= (t & 8) << 11;
            t &= 7;
            if (t == 0)
            {
                NEED_IP(1);
                while (*ip == 0)
                {
                    t += 255;
                    ip++;
                    NEED_IP(1);
                }
                t += 7 + *ip++;
            }
            t += 2;

            NEED_IP(2);
            m_pos -= (*(const ushort *)ip) >> 2;
            ip += 2;
            if (m_pos == op)
                goto eof_found;
            m_pos -= 0x4000;
        }
        else if (t == M1_MARKER) /* a M1 match */
        {
            NEED_IP(4);
            t = *(uint *)ip;
            ip += 4; 

            m_pos = op - (t >> 1);

            if((t & 1) == 1) 
            {
                NEED_IP(4);
                t = *(ushort *)ip << 14;
                ip += 2;

                t += *(ushort *)ip >> 2;
                ip += 2;
            }
            else
            {
                NEED_IP(2);
                t = *(ushort *)ip >> 2;
                ip += 2;
            }
        }

        /* copy match */
        TEST_LB(m_pos); ASSERT(t > 2); NEED_OP(t);
        MEMCPY(op, m_pos, t);

        /* handle R3 run */
        t = ip[-2] & 3;
        if (t != 0)
        {
            /* copy literals */
            ASSERT(t > 0); 
            ASSERT(t < 4); 
            NEED_OP(t); NEED_IP(t + 1);

            switch((uchar)t)
            {
                case 3: *op++ = *ip++;
                case 2: *op++ = *ip++;
                case 1: *op++ = *ip++;
            }   
        }
        if((op - out) % 1000000 < 50)
            fprintf(stderr, "op=%p, out_len=%d\n", op, *out_len);
    }

    *out_len = (uint)(op - out);
    return PP_E_EOF_NOT_FOUND;

eof_found:
    ASSERT(t == 3);
    *out_len = (uint)(op - out);
    return (ip == ip_end ? PP_E_OK :
            (ip < ip_end  ? PP_E_INPUT_NOT_CONSUMED : PP_E_INPUT_OVERRUN));

input_overrun:
    *out_len = (uint)(op - out);
    return PP_E_INPUT_OVERRUN;

output_overrun:
    *out_len = (uint)(op - out);
    return PP_E_OUTPUT_OVERRUN;

lookbehind_overrun:
    *out_len = (uint)(op - out);
    return PP_E_LOOKBEHIND_OVERRUN;
}

/*
 * free pplz hash dict 
 */
void pplz_free(pplz_hash_t *ph)
{
    if(ph)
    {
        free(ph->s_dict);
        free(ph->l_dict);
    }
}


/*  alloc memory for pplz hash table 
 *  8M * sizeof(char *)
 *  128k * sizeof(char *) 
 *  is needed
 *
 *  return NULL, if fails
 */
pplz_hash_t *pplz_new()
{
    pplz_hash_t *ph;
   
    ph = (pplz_hash_t *)malloc(sizeof(pplz_hash_t));
    if(ph == NULL)
    {
        goto out;
    }
    ph->s_dict = (const uchar **)malloc(sizeof(uchar *) * S_HASH_SIZE);
    if(ph->s_dict == NULL)
    {
        goto out;
    }
    ph->l_dict = (const uchar **)malloc(sizeof(uchar *) * L_HASH_SIZE);
    if(ph->l_dict == NULL)
    {
        goto out;
    }
    return ph;
out:
    pplz_free(ph);
    return NULL;
}


